<?php 
	error_reporting(E_ALL);

	//TODO:Check functions used only once
	class Direction
	{
		const UP	=	0;
		const RIGHT	=	1;
		const DOWN	=	2;
		const LEFT	=	3;

		const TOTAL_DIRECTIONS	=	4;

		private static $previousDirection	=	Direction::UP;
		private $directionsPicked			=	array();
		private $directionModifier			=	0;

		//TODO:set previousDirection on constructor
		public function __construct($directionModifier)
		{
			$this->directionModifier	=	$directionModifier;
		}

		public function hasNextDirection()
		{
			return count($this->directionsPicked) < Direction::TOTAL_DIRECTIONS;
		}

		public function getNextDirection()
		{
			if (!$this->hasNextDirection())
			{
				throw new Exception('No directions available.');
			}

			do
			{

				$directionPicked	=	$this->mustChangeDirection() ? $this->pickDifferentDirection() : self::$previousDirection;
			} while (in_array($directionPicked, $this->directionsPicked));

			self::$previousDirection	=	$directionPicked;

			array_push($this->directionsPicked, $directionPicked);

			return $directionPicked;
		}

		public static function setPreviousDirection($direction)
		{
			self::$previousDirection	=	$direction;
		}

		public static function isValidDirection($direction)
		{
			return $direction >= 0 && $direction <= Direction::TOTAL_DIRECTIONS-1;
		}

		private function mustChangeDirection()
		{
			return count($this->directionsPicked) || $this->directionModifier > mt_rand(0,99);
		}

		private function pickDifferentDirection()
		{
			do
			{
				$directionPicked	=	mt_rand(0, Direction::TOTAL_DIRECTIONS - 1);
			} while($directionPicked == self::$previousDirection && count($this->directionsPicked) < Direction::TOTAL_DIRECTIONS-1);

			return $directionPicked;
		}
	};

	class SideType
	{
		const NOTHING	=	0;
		const WALL		=	1;
	};

	class Point
	{
		public $x;
		public $y;

		public function __construct($x, $y)
		{
			$this->x	=	$x;
			$this->y	=	$y;
		}
	};

	class Cell
	{
		public $visited		=	false;
		public $isCorridor 	=	false;
		public $sides		=	array();//NOTE: Code with sides as array
		
/*
		//NOTE: Code with sides as individual properties
		public $sideUp		=	SideType::WALL;
		public $sideRight	=	SideType::WALL;
		public $sideDown	=	SideType::WALL;
		public $sideLeft	=	SideType::WALL;
*/
		public function __construct()
		{
			//NOTE: Code with sides as array
			for ($i=0; $i<Direction::TOTAL_DIRECTIONS; $i++)
			{
				array_push($this->sides, SideType::WALL);
			}
		}

		public function isDeadEnd()
		{
			return $this->wallCount() == 3;
		}

		public function wallCount()
		{
			$wallCount	=	0;

			//NOTE: Code with sides as array
			for ($i=0; $i<Direction::TOTAL_DIRECTIONS; $i++)
			{
				if ($this->sides[$i] == SideType::WALL)
				{
					$wallCount++;
				}
			}

/*
			//NOTE: Code with sides as individual properties
			$wallCount	+=	$this->sideUp		==	SideType::WALL ? 1 : 0;
			$wallCount	+=	$this->sideRight	==	SideType::WALL ? 1 : 0;
			$wallCount	+=	$this->sideDown		==	SideType::WALL ? 1 : 0;
			$wallCount	+=	$this->sideLeft		==	SideType::WALL ? 1 : 0;
*/

			return $wallCount;
		}

		public function getDeadEndCorridorDirection()
		{
			if (!$this->isDeadEnd())
			{
				throw new Exception('Cell is not a dead end.');
			}

			//NOTE: Code with sides as array
			for ($i=0; $i<Direction::TOTAL_DIRECTIONS; $i++)
			{
				if ($this->sides[$i] == SideType::NOTHING)
				{
					$direction	=	$i;
					break;
				}
			}

			if (!isset($direction))
			{
				throw new Exception('Dead end cell has empty side.');
			}

/*
			//NOTE: Code with sides as individual properties
			if ($this->sideUp == SideType::NOTHING)
			{
				$direction	=	Direction::UP;
			}
			elseif ($this->sideRight == SideType::NOTHING)
			{
				$direction	=	Direction::RIGHT;
			}
			elseif ($this->sideDown == SideType::NOTHING)
			{
				$direction	=	Direction::DOWN;
			}
			elseif ($this->sideLeft == SideType::NOTHING)
			{
				$direction	=	Direction::LEFT;
			}
			else
			{
				throw new Exception('Dead end cell has empty side.');
			}
*/

			return $direction;
		}
		
	};
	class Room
	{
		private $cells	=	array();
		private $width;
		private $height;
				
		public function initializeRoomCells()
		{
			for($x = 0; $x < $this->getWidth(); $x++)
            {
                  
                for($y = 0; $y < $this->getHeight(); $y++)
                {
                    $cell = new Cell();
                   
                    $cell[Direction::UP] 	= 	$y == 0 ? SideType::WALL:SideType::NOTHING;
                	$cell[Direction::RIGHT] =	$x == ($this->getWidth()-1) ? SideType::WALL:SideType::NOTHING;
                	$cell[Direction::DOWN] 	= 	$y == ($this->getHeight()-1) ? SideType::WALL:SideType::NOTHING;
                	$cell[Direction::LEFT] 	=	$x == 0 ? SideType::WALL:SideType::NOTHING;
 					$this->cells[$x][$y]    =	$cell;    
 			     }
             }
		}
		public function getWidth()
		{
			return $this->width;
		}
		public function getHeight()
		{
			return $this->height;
		}
	}
	class Map
	{
		private $cells			=	array();
		private $visitedPoints	=	array();
		private $width;
		private $height;
		
		public function __construct($width, $height, $directionModifier, $sparsenessModifier, $deadEndRemovalModifier)
		{
			$this->width	=	$width;
			$this->height	=	$height;

			for ($i=0; $i<$width; $i++)
			{
				$column =	array ();

				for ($j=0; $j<$height; $j++)
				{
					$cell	=	new Cell();

					array_push($column, $cell);
				}

				array_push($this->cells, $column);
			}

			$this->createDenseMaze($directionModifier);
			$this->sparsifyMaze($sparsenessModifier);
			$this->removeDeadEnds($deadEndRemovalModifier);
			
		}

		private function createDenseMaze($directionModifier)
		{
			$currentLocation	=	$this->pickRandomCellAndMarkItVisited();

			while (!$this->allCellsVisited())
			{
				$directionPicker	=	new Direction($directionModifier);
				$directionPicked	=	$directionPicker->getNextDirection();

				while(!$this->hasAdjacentCellInDirection($currentLocation, $directionPicked) || $this->adjacentCellInDirectionIsVisited($currentLocation, $directionPicked))
				{
					if ($directionPicker->hasNextDirection())
					{
						$directionPicked	=	$directionPicker->getNextDirection();
					}
					else
					{
						$currentLocation	=	$this->getRandomVisitedLocation($currentLocation);
						$directionPicker	=	new Direction($directionModifier);
						$directionPicked	=	$directionPicker->getNextDirection();
					}
				}

				$currentLocation	=	$this->createCorridor($currentLocation, $directionPicked);

				$this->flagCellAsVisited($currentLocation);
			}
		}

		private function allCellsVisited()
		{
			return count($this->visitedPoints) == $this->width * $this->height;
		}

		private function isValidLocation(Point $point)
		{
			return !($point->x < 0 || $point->x > $this->width - 1 || $point->y < 0 || $point->y > $this->height - 1);
		}

		public function getCell(Point $point)
		{
			if (!$this->isValidLocation($point))
			{
				throw new Exception('Coordinate out of bounds.');
			}

			return $this->cells[$point->x][$point->y];
		}

		public function getWidth()
		{
			return $this->width;
		}

		public function getHeight()
		{
			return $this->height;
		}

		private function flagCellAsVisited(Point $point)
		{
			//TODO:Is it really needed? Under what kind of circumstances $point may be out of bounds?
			if (!$this->isValidLocation($point))
			{
				throw new Exception('Location is outside of Map bounds.');
			}

			if ($this->getCell($point)->visited)
			{
				throw new Exception('Location is already visited.');
			}

			$this->cells[$point->x][$point->y]->visited	=	true;
			
			array_push($this->visitedPoints, $point);
		}

		private function pickRandomCellAndMarkItVisited()
		{
			$x		=	mt_rand(0, $this->width - 1);
			$y		=	mt_rand(0, $this->height - 1);
			$point	=	new Point($x, $y);

			$this->cells[$x][$y]->visited	=	true;

			array_push($this->visitedPoints, $point);

			return $point;
		}

		private function getRandomVisitedLocation(Point $point)
		{
			$totalVisitedPoints	=	count($this->visitedPoints);

			if (!$totalVisitedPoints)
			{
				throw new Exception('There are no visited cells to return.');
			}

			$index	=	mt_rand(0, $totalVisitedPoints - 1);

			while ($this->visitedPoints[$index] === $point)
			{
				$index	=	mt_rand(0, $totalVisitedPoints - 1);
			}

			return $this->visitedPoints[$index];
		}

		private function hasAdjacentCellInDirection(Point $point, $direction)
		{
			if (!Direction::isValidDirection($direction))
			{
				throw new Exception('Invalid direction.');
			}

			$output	=	false;

			if($this->isValidLocation($point))
			{
				switch ($direction)
				{
					case Direction::UP:
						$output	=	$point->y > 0;
						break;
					case Direction::RIGHT:
						$output	=	$point->x < $this->width - 1;
						break;
					case Direction::DOWN:
						$output	=	$point->y < $this->height - 1;
						break;
					case Direction::LEFT:
						$output	=	$point->x > 0;
						break;
				}
			}

			return $output;
		}

		private function adjacentCellInDirectionIsVisited(Point $point, $direction)
		{
			if (!Direction::isValidDirection($direction))
			{
				throw new Exception('Invalid direction.');
			}
/*
			//TODO:Is it really needed to call this? Constructor algorithm already call hasAdjacentCellInDirection before calling adjacentCellInDirectionIsVisited
			if (!$this->hasAdjacentCellInDirection($point, $direction))
			{
				throw new Exception('No adjacent cell exists for the location and direction provided.');
			}
*/
			$newPoint	=	clone $point;

			switch ($direction)
			{
				case Direction::UP:
					$newPoint->y--;
					break;
				case Direction::RIGHT:
					$newPoint->x++;
					break;
				case Direction::DOWN:
					$newPoint->y++;
					break;
				case Direction::LEFT:
					$newPoint->x--;
					break;
			}

			return $this->getCell($newPoint)->visited;
		}

		private function getTargetLocation(Point $point, $direction)
		{
			if (!Direction::isValidDirection($direction))
			{
				throw new Exception('Invalid direction.');
			}

			if (!$this->hasAdjacentCellInDirection($point, $direction))
			{
				throw new Exception('No adjacent cell exists for the location and direction provided.');
			}

			$x	=	$point->x;
			$y	=	$point->y;

			switch($direction)
			{
				case Direction::UP:
					$y--;
					break;
				case Direction::RIGHT:
					$x++;
					break;
				case Direction::DOWN:
					$y++;
					break;
				case Direction::LEFT:
					$x--;
					break;
			}
			
			return new Point($x, $y);
		}

		private function createCorridor(Point $point, $direction)
		{
			return $this->createSide($point, $direction, SideType::NOTHING);
		}

		private function createWall(Point $point, $direction)
		{
			return $this->createSide($point, $direction, SideType::WALL);
		}

		private function createSide(Point $point, $direction, $sideType)
		{
			//TODO:Check where Direction::isValidDirection is really needed, not only here but wherever is used
			if (!Direction::isValidDirection($direction))
			{
				throw new Exception('Invalid direction.');
			}

			$adjacentPoint	=	$this->getTargetLocation($point, $direction);

/*
			//NOTE: Code with sides as individual properties
			switch($direction)
			{
				case Direction::UP:
					$pointSide			=	'sideUp';
					$adjacentPointSide	=	'sideDown';
					break;
				case Direction::RIGHT:
					$pointSide			=	'sideRight';
					$adjacentPointSide	=	'sideLeft';
					break;
				case Direction::DOWN:
					$pointSide			=	'sideDown';
					$adjacentPointSide	=	'sideUp';
					break;
				case Direction::LEFT:
					$pointSide			=	'sideLeft';
					$adjacentPointSide	=	'sideRight';
					break;
			}

			$this->getCell($point)->$pointSide					=	$sideType;
			$this->getCell($adjacentPoint)->$adjacentPointSide	=	$sideType;
*/
			//NOTE: Code with sides as array
			$oppositeDirection											=	($direction + 2) % 4;
			$this->getCell($point)->sides[$direction]					=	$sideType;
			$this->getCell($adjacentPoint)->sides[$oppositeDirection]	=	$sideType;

			return $adjacentPoint;
		}

		public function getDeadEndCellLocations()
		{
			$deadEndCellLocations	=	array();

			for ($i=0; $i<$this->width; $i++)
			{
				for ($j=0; $j<$this->height; $j++)
				{
					$point	=	new Point($i, $j);

					if ($this->getCell($point)->isDeadEnd())
					{
						array_push($deadEndCellLocations, $point);
					}
				}
			}

			return $deadEndCellLocations;
		}

		public function sparsifyMaze($sparsenessModifier)
		{

			$deadEndCellLocations			=	$this->getDeadEndCellLocations();
			$noOfDeadEndCellsToRemove		= 	ceil($sparsenessModifier / 100 * ($this->width * $this->height));
			$deadEndCellLocationsIndex 		= 	-1;

			for ($i = 0; $i < $noOfDeadEndCellsToRemove; $i++)
			{
				if(!isset($deadEndCellLocations[++$deadEndCellLocationsIndex]))
				{
					$deadEndCellLocationsIndex 		= 	-1;
					$deadEndCellLocations			=	$this->getDeadEndCellLocations();

					if(!isset($deadEndCellLocations[++$deadEndCellLocationsIndex]))
					{
						break;
					}
				}

 				$point	=	$deadEndCellLocations[$deadEndCellLocationsIndex];

				$this->createWall($point, $this->getCell($point)->getDeadEndCorridorDirection());
			}
		}

		public static function shouldRemoveDeadEnd($deadEndRemovalModifier)
		{
			return mt_rand(1,99) < $deadEndRemovalModifier;
		}

		public function removeDeadEnds($deadEndRemovalModifier)
		{
			$deadEndCellLocations	=	$this->getDeadEndCellLocations();

			foreach($deadEndCellLocations as $deadEndCellLocation)
			{
				if (self::shouldRemoveDeadEnd($deadEndRemovalModifier))
				{
					$point	=	$deadEndCellLocation;
					$cell	=	$this->getCell($point);

					do
					{

						Direction::setPreviousDirection($cell->getDeadEndCorridorDirection());

						$directionPicker	=	new Direction(100);
						$nextDirection		=	$directionPicker->getNextDirection();


						while (!$this->hasAdjacentCellInDirection($point, $nextDirection))
						{
							if ($directionPicker->hasNextDirection())
							{
								$nextDirection	=	$directionPicker->getNextDirection();

							}
							else
							{
								throw new Exception('This should not happen.');
							}
						}

						$point	=	$this->createCorridor($point, $nextDirection);
						$cell	=	$this->getCell($point);

					} while ($cell->isDeadEnd());

				}

			}
		}
		public function createRoom($minRoomWidth, $maxRoomWidth, $minRoomHeight, $maxRoomHeight)
		{
			$room = new Room(mt_rand($this->minRoomWidth, $this->maxRoomWidth), mt_rand($this->minRoomHeight, $this->maxRoomHeight));
			$room->initializeRoomCells();
			return $room;
		}
		
	};